package com.algo.moduleFour;

import java.util.PriorityQueue;

/**
 * 滑动窗口
 */
public class MaxSlidingWindow {

    public int[] maxSlidingWindow(int[] nums, int k) {
        // 优先队列维护窗口 用数组存放->[关键码，下标]
        PriorityQueue<int[]> q = new PriorityQueue<>(nums.length, (o1, o2) -> Integer.compare(o2[0] - o1[0], 0));
        // 答案存放 ，
        int[] ans = new int[nums.length - k + 1];
        for (int i = 0; i < nums.length; i++) {

            q.add(new int[]{nums[i],i});
            if(i >= k-1){
                // 懒得删除（只有最大堆顶 在窗口外才删除）[i-k+1, i]
                while (q.peek()[1] <= i - k ) {
                    q.poll();
                }
                //
                ans[i-k+1] = q.peek()[0];

            }
        }

        return ans;
    }
}
